(1) Field of the Invention
The invention generally relates to signal processing/data processing systems for processing time series distributions containing a small number of data points (e.g., less than about ten (10) to fifteen (15) data points). More particularly, the invention relates to a method and apparatus for classifying the white noise degree (randomness) of a selected signal structure comprising a three dimensional time series distribution composed of a highly sparse data set. As used herein, the term xe2x80x9crandomxe2x80x9d(or xe2x80x9crandomnessxe2x80x9d) is defined in terms of a xe2x80x9crandom processxe2x80x9d as measured by the probability distribution model used, namely a nearest-neighbor stochastic (Poisson) process. Thus, pure randomness, pragmatically speaking, is herein considered to be a time series distribution for which no function, mapping or relation can be constituted that provides meaningful insight into the underlying structure of the distribution, but which at the same time is not chaos.
(2) Description of the Prior Art
Recent research has revealed a critical need for highly sparse data set time distribution analysis methods and apparatus separate and apart from those adapted for treating large sample distributions. This is particularly the case in applications such as naval sonar systems, which require that input time series signal distributions be classified according to their structure, i.e., periodic, transient, random or chaotic. It is well known that large sample methods often fail when applied to small sample distributions, but that the same is not necessarily true for small sample methods applied to large data sets. Very small data set distributions may be defined as those with less than about ten (10) to fifteen (15) measurement (data) points. Such data sets can be analyzed mathematically with certain nonparametric discrete probability distributions, as opposed to large-sample methods, which normally employ continuous probability distributions (such as the Gaussian).
The probability theory discussed herein and utilized by the present invention is well known. It may be found, for example, in works such as P. J. Hoel et al., Introduction to the Theory of Probability, Houghton-Mifflin, Boston, Mass., 1971, which is hereby incorporated herein by reference.
Also, as will appear more fully below, it has been found to be important to treat white noise signals themselves as the time series signal distribution to be analyzed, and to identify the characteristics of that distribution separately. This aids in the detection and appropriate processing of received signals in numerous data acquisition contexts, not the least of which include naval sonar applications. Accordingly, it will be understood that prior analysis methods and apparatus analyze received time series data distributions from the point of view of attempting to find patterns or some other type of correlated data therein. Once such a pattern or correlation is located, the remainder of the distribution is simply discarded as being noise. It is believed that the present invention will be useful in enhancing the sensitivity of present analysis methods, as well as being useful on its own.
Previous U.S. Pat. No. 6,397,234 recited a method and apparatus for characterizing the spatial arrangement among the data points of a two dimensional time series distribution, e.g., sonar signal frequency over time. A large number of applications require processing three dimensional time series distributions, e.g., tracking the landing approach of an aircraft, missile tracking, or including a spatial dimension with the sonar distribution to assist in tracking a submarine. Thus, a need has been determined for providing a method and apparatus for characterizing the spatial arrangement among the data points of a three dimensional time series distribution.
Accordingly, it is an object of the invention to provide a method and apparatus including an automated measurement of the three dimensional spatial arrangement among a very small number of points, objects, measurements or the like whereby an ascertainment of the noise degree (i.e., randomness) of the time series distribution may be made.
It also is an object of the invention to provide a method and apparatus useful in naval sonar, radar and lidar and in aircraft and missile tracking systems, which require acquired signal distributions to be classified according to their structure (i.e., periodic, transient, random, or chaotic) in the processing and use of those acquired signal distributions as indications of how and from where they were originally generated.
Further, it is an object of the invention to provide a method and apparatus capable of labeling a three dimensional time series distribution with (1) an indication as to whether or not it is random in structure, and (2) an indication as to whether or not it is random within a probability of false alarm of a specific randomness calculation.
With the above and other objects in view, as will hereinafter more fully appear, a feature of the invention is the provision of a random process detection method and subsystem for use in a signal processing/data processing system. In a preferred embodiment, the random process (white noise) detection subsystem includes an input for receiving a three-dimensional time series distribution of data points expressed in Cartesian coordinates. This set of data points will be characterized by no more than a maximum number of points having values (amplitudes) between maximum and minimum values received within a preselected time interval. A hypothetical representation of a white noise time series signal distribution in Cartesian space is illustratively shown in FIG. 1. The invention is specifically adapted to analyze both selected portions of such time series distributions, and the entirety of the distribution depending upon the sensitivity of the randomness determination, which is required in any particular instance.
The input time series distribution of data points is received by a display/operating system adapted to accommodate a pre-selected number of data points N in a pre-selected time interval xcex94t and dispersed in three-dimensional space along with a first measure referred to as Y with magnitude xcex94Y=max(Y)xe2x88x92min(Y), and a second measure referred to as Z with magnitude xcex94Z=max(Z)xe2x88x92min(Z). The display/operating system then creates a virtual volume around the input data distribution and divides the virtual volume into a grid consisting of cubic cells each of equal enclosed volume. Ideally, the cells fill the entire virtual volume, but if they do not, the unfilled portion of the virtual volume is disregarded in the randomness determination.
An analysis device then examines each cell to determine whether or not one or more of the data points of the input time series distribution are located therein. Thereafter, a counter calculates the number of occupied cells. Also, the number of cells which would be expected to be occupied in the grid for a totally random distribution is predicted by a computer device according to known Poisson probability process theory equations. In addition, the statistical bounds of the predicted value are calculated based upon known discrete binomial criteria.
A comparator is then used to determine whether or not the actual number of occupied cells in the input time series distribution is the same as the predicted number of cells for a random distribution. If it is, the input time series distribution is characterized as random. If it is not, the input time series distribution is characterized as nonrandom.
Thereafter, the characterized time series distribution is labeled as random or nonrandom, and/or as random or nonrandom within a pre-selected probability rate of the expected randomness value prior to being output back to the remainder of the data processing system. In the naval sonar signal processing context, this output either alone, or in combination with overlapping similarly characterized time series signal distributions, will be used to determine whether or not a particular group of signals is white noise. If that group of signals is white noise, it commonly will be deleted from further data processing. Hence, it is contemplated that the present invention, which is not distribution dependent in its analysis as most prior art methods of signal analysis are, will be useful as a filter or otherwise in conjunction with current data processing methods and equipment.
In the above regards, it should be understood that the statistical bounds of the predicted number of occupied cells in a random distribution (including cells occupied by mere chance) mentioned above may be determined by a second calculator device using a so-called probability of false alarm rate. In this case, the actual number of occupied cells is compared with the number of cells falling within the statistical boundaries of the predicted number of occupied cells for a random distribution in making the randomness determination. This alternative embodiment of the invention has been found to increase the probability of being correct in making a randomness determination for any particular time series distribution of data points by as much as 60%.
The above and other novel features and advantages of the invention, including various novel details of construction and combination of parts will now be more particularly described with reference to the accompanying drawings and pointed out by the claims. It will be understood that the particular device and method embodying the invention is shown and described herein by way of illustration only, and not as limitations on the invention. The principles and features of the invention may be employed in numerous embodiments without departing from the scope of the invention in its broadest aspects.